%Porównanie algorytmów stosowanych do rozwiązywania problemu opisywanych we współczesnej literaturze

\section{Opis testu}
Wcześniej opisane metody zostały przetestowane na 20 planszach o wymiarach $15\times 15$, wypełnionymi klockami w~5~kolorach zgodnie z charakterystyką:
\begin{itemize}
\item plansze 1-10 zostały wygenerowane losowo,
\item plansze 11-15 są zbalansowane i posiadają po 45 klocków w każdym z kolorów,
\item na pozostałych planszach dominuje jeden z kolorów.
\end{itemize}

\section{Wyniki}
\begin{table}[!ht]
\begin{tabular}{|c||c|c|c|c|c|}
\hline
Puzzle & Brute force & DBS			& MC-Biggest	& MC-Avg 	& Alg. SP-MCTS	\\
\hline
\hline
1 	& \texttt{443}	& \texttt{2 061}& \texttt{723}	& \texttt{1 771}& \texttt{2 557}	\\
\hline
2	& \texttt{831}	& \texttt{3 513}& \texttt{1 369}& \texttt{2 585}& \texttt{3 749}	\\
\hline
3	& \texttt{641}	& \texttt{3 151}& \texttt{1 497}& \texttt{2 481}& \texttt{3 085}	\\
\hline
4	& \texttt{709}	& \texttt{3 653}& \texttt{1 521}& \texttt{3 247}& \texttt{3 641}	\\
\hline
5	& \texttt{533}	& \texttt{3 093}& \texttt{1 601}& \texttt{2 641}& \texttt{3 653}	\\
\hline
6 	& \texttt{903}	& \texttt{4 101}& \texttt{2 393}& \texttt{3 013}& \texttt{3 971}	\\
\hline
7	& \texttt{487}	& \texttt{2 507}& \texttt{947}	& \texttt{2 271}& \texttt{2 791}	\\
\hline
8	& \texttt{1 367}& \texttt{3 819}& \texttt{2 291}& \texttt{3 433}& \texttt{3 715}	\\
\hline
9	& \texttt{1 385}& \texttt{4 649}& \texttt{2 731}& \texttt{4 189}& \texttt{4 603}	\\
\hline
10	& \texttt{459}	& \texttt{3 199}& \texttt{1 335}& \texttt{2 585}& \texttt{3 213}	\\
\hline
\hline
11 	& \texttt{491}	& \texttt{2 911}& \texttt{1 219}& \texttt{2 167}& \texttt{3 047}	\\
\hline
12	& \texttt{689}	& \texttt{2 979}& \texttt{1 607}& \texttt{2 535}& \texttt{3 131}	\\
\hline
13	& \texttt{613}	& \texttt{3 209}& \texttt{1 165}& \texttt{2 283}& \texttt{3 097}	\\
\hline
14	& \texttt{575}	& \texttt{2 685}& \texttt{1 209}& \texttt{2 401}& \texttt{2 859}	\\
\hline
15	& \texttt{839}	& \texttt{3 259}& \texttt{1 567}& \texttt{2 831}& \texttt{3 183}	\\
\hline
\hline
16 	& \texttt{2 267}& \texttt{4 765}& \texttt{3 509}& \texttt{4 533}& \texttt{4 879}	\\
\hline
17	& \texttt{817}	& \texttt{4 447}& \texttt{2 837}& \texttt{3 355}& \texttt{4 609}	\\
\hline
18	& \texttt{1 167}& \texttt{5 099}& \texttt{3 239}& \texttt{4 497}& \texttt{4 853}	\\
\hline
19	& \texttt{1 471}& \texttt{4 865}& \texttt{2 041}& \texttt{3 323}& \texttt{4 503}	\\
\hline
20	& \texttt{943}	& \texttt{4 851}& \texttt{2 855}& \texttt{2 811}& \texttt{4 853}	\\
\hline
\hline
\textbf{Total} & \textbf{17 610}	& \textbf{72 816} & \textbf{37 656}	& \textbf{58 952} & \textbf{73 998} \\
\hline
\end{tabular}\centering
\caption{Porównanie działania algorytmów wg. zdobytych punktów \cite{samegame-solving} .}
\label{tab:tab1}
\end{table}

\subsection{Brute force}
Zgodne z oczekiwaniami najgorszym algorytmem okazał się Brute force, czyli losowe wybierane. Algorytm ten w żaden sposób nie stara się maksymalizować rezultatów otrzymywanych po poszczególnych kliknięciach, co powoduje powstawanie wielu nierozwiązywalnych układów klocków i przekłada się na kiepski wynik w teście, którego wyniki zostały zawarte w tabeli \ref{tab:tab1}.

\subsection{Depth-Budgeted Search}
Metoda DBS będąca wariantem algorytmu bankiera, zwróciła bardzo dobre rezultaty, co pozwoliło jej zająć drugie miejsce w teście pod względem średniej jakości wyników. Zastosowanie innowacyjnego podejścia opartego na budżecie okazało się bardzo efektywne dla omawianego problemu, który cechuje się dużą złożonością co wyklucza prostą analizę.

\subsection{MC-Biggest}
Metoda MC-Biggest jest odmianą algorytmu Monte Carlo, która dla obecnego węzła rozsyła do jego dzieci określoną liczbę próbek, a następnie wybiera następny krok na podstawie najlepszej próbki. Patrząc do tabeli \ref{tab:tab1} łatwo zauważyć, że ta metoda również nie cechuje się wysoką średnią skutecznością, ze względu na duży udział losowości przy generowaniu rozwiązania.

\subsection{MC-Avg}
Metoda MC-Avg bazuje na tej samej idei co MC-Biggest z wyjątkiem zmienionego warunku wyboru następnego kroku, który jest wybierany na podstawie średniej osiągniętej przez wszystkie próbki wysłane do dzieci węzła. Pozwala to uniknąć rozwiązań suboptymalnych i choć niestety również może wykluczyć najlepsze rozwiązanie, jest to mało prawdopodobne. Rozwiązanie to uklasyfikowało się na trzeciej pozycji w przeprowadzonym teście.

\subsection{MSP-MCTS}
SP-MCTS jest metodą szukającą najlepszego dopasowania, która nie wymaga pozycyjnej funkcji oceny. Zamiast tego buduje ona drzewo w którym każdy z węzłów reprezentuje wybierany blok na planszy, średni wynik osiągany dla niego i liczbę przejść przez dany węzeł. Opiera się ona na doborze najlepszego pod względem jakości węzła. Przy użyciu tego algorytmu uzyskano jedne z najlepszych wyników i najlepsze średnie wyniki ze wszystkich metod.